package com.datastructures2.search;

/**
 * @author MaoLin Wang
 * @date 2020/4/109:45
 */
public class BS<Key extends Comparable<? super Key>,Value> {

    private Key[]keys;
    private Value[]values;
    private int size;

    public BS(int size) {
        this.keys= (Key[]) new Comparable[size];
        this.values= (Value[]) new Comparable[size];
    }

    public Value find(Key key){
        if (isEmpty()){
            return null;
        }
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            return values[i];
        }else {
            return null;
        }


    }

    private boolean isEmpty() {
        return size==0;
    }

    private int rank(Key key) {
        int left=0;
        int right=size-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            int result=key.compareTo(keys[mid]);
            if (result<0){
                right=mid-1;
            }else if (result>0){
                left=mid+1;
            }else {
                return mid;
            }
        }
        return left;
    }
    public void put(Key key,Value value){
        if (key==null){
            return;
        }
        if (value==null){
             delete(key);
             return;
        }
        int i=rank(key);
        if (i<size&&keys[i].compareTo(key)==0){
            values[i]=value;
        }else {
            if(size==keys.length){
                resize(2*size-1);

            }
            for (int j = size; j >i ; j--) {
                keys[j]=keys[j-1];
                values[j]=values[j-1];
            }
            keys[i]=key;
            values[i]=value;
            size++;
        }
    }

    private void delete(Key key) {
        if (key==null){
            return;
        }
        int i=rank(key);
        if (i<size&&keys[i].compareTo(key)==0){
            for (int j = i; j <size ; j++) {
                keys[j]=keys[j+1];
                values[j]=values[j+1];
            }
            keys[size]=null;
            values[size]=null;
            size--;
        }
    }

    private void resize(int capacity) {
        Key[]newKey= (Key[]) new Comparable[capacity];
        Value[]newValue= (Value[]) new Comparable[capacity];
        for (int i = 0; i < size; i++) {
            newKey[i]=keys[i];
            newValue[i]=values[i];
        }
        keys=newKey;
        values=newValue;
    }

    public static void main(String[] args) {
        BS<Integer,String> bs=new BS(4);
        bs.put(1,"wml");
        bs.put(5,"wml5");
        bs.put(3,"wml3");
        bs.put(2,"wml2");
        bs.put(4,"wml4");
        bs.put(6,"wml6");
        bs.put(7,"wml7");

        System.out.println(bs.find(5));
        System.out.println(bs.find(1));
        System.out.println(bs.find(3));
        System.out.println(bs.find(7));

    }
}
